package 牛客;

public class pJZ36二叉搜索树与双向链表 {
    //双向链表有三个域，而每个节点也有三个域，我们可以自己规定left代表prev，right代表next
    //根据二叉搜索树的中序遍历结果，确定前后驱关系，那么双向链表也就确定了，返回双向链表的头即可
    //代码重点：根据中序遍历，每遍历到一个节点 就要修改当前节点的左引用和右引用，即前后驱关系
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null) return null;

        ConvertChild(pRootOfTree);//传入根节点，按照中序遍历构造双向链表
        TreeNode head=pRootOfTree;//用来返回双向链表的头节点
        while (head.left!=null) {
            head=head.left;
        }
        return head;
    }

    public static TreeNode prev=null;
    public void ConvertChild(TreeNode pCur) {

        //不仅要实现中序遍历，关键在于通过中序遍历确定遍历节点的前后驱关系，从而实现双向链表
        if (pCur==null) return;
        ConvertChild(pCur.left);

        //打印 System.out.println(pCur.val+" ");
        pCur.left=prev;
        if (prev!=null) {
            prev.right=pCur;
        }
        prev=pCur;

        ConvertChild(pCur.right);
    }
}
